package 动态规划.最大子序和;

public class 最大子序和_53 {

    class Solution {
        public int maxSubArray(int[] nums) {
            if (nums.length == 0) {
                return 0;
            }
            int N = nums.length;
            //dp[i]：以nums[i]结尾的“最大子数组和”，可以对照“最长递增子序列”中dp[i]的定义
            int[] dp = new int[N];

            //base case
            dp[0] = nums[0];//第一个元素前面没有子数组，所以最大和就是它本身

            for (int i = 1; i < N; i++) {
                //要么自成一派，要么和前面的子数组合并
                dp[i] = Math.max(nums[i], dp[i - 1] + nums[i]);
            }

            int res = Integer.MIN_VALUE;
            for (int i = 0; i < dp.length; i++) {
                res = Math.max(res, dp[i]);
            }

            return res;
        }
    }
}
